package seqlist.leetcode;

//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//你不需要 保留 每个分区中各节点的初始相对位置。
public class interview_0204_partition {
    public ListNode partition(ListNode head, int x) {
        if(head==null){
            return null;
        }

        ListNode smileHead = new ListNode();
        ListNode smiletail = smileHead;
        ListNode bigHead = new ListNode();
        ListNode bigTail = bigHead;
        while (head != null) {
            if (head.val < x) {
                smiletail.next = head;
                smiletail = head;
            } else {
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        bigTail.next=null;
        smiletail.next=bigHead.next;
        return smileHead.next;
    }
}
